package com.starcor.xul.Utils;

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

/**
 * Created by hy on 2015/6/8.
 */
public class XulArrayList<E> extends AbstractList<E> implements Cloneable, Serializable, RandomAccess {
	/**
	 * The minimum amount by which the capacity of an ArrayList will increase.
	 * This tuning parameter controls a time-space tradeoff. This value (12)
	 * gives empirically good results and is arguably consistent with the
	 * RI's specified default initial capacity of 10: instead of 10, we start
	 * with 0 (sans allocation) and jump to 12.
	 */
	private static final int MIN_CAPACITY_INCREMENT = 12;

	/**
	 * The number of elements in this list.
	 */
	int size;

	/**
	 * The elements in this list, followed by nulls.
	 */
	transient Object[] array;

	private static final Object[] EMPTY_ARRAY = new Object[0];

	/**
	 * Constructs a new instance of {@code ArrayList} with the specified
	 * initial capacity.
	 *
	 * @param capacity the initial capacity of this {@code ArrayList}.
	 */
	public XulArrayList(int capacity) {
		if (capacity < 0) {
			throw new IllegalArgumentException("capacity < 0: " + capacity);
		}
		array = capacity == 0 ? EMPTY_ARRAY : new Object[capacity];
	}

	/**
	 * Constructs a new {@code ArrayList} instance with zero initial capacity.
	 */
	public XulArrayList() {
		array = EMPTY_ARRAY;
	}

	/**
	 * Constructs a new instance of {@code ArrayList} containing the elements of
	 * the specified collection.
	 *
	 * @param collection the collection of elements to add.
	 */
	public XulArrayList(Collection<? extends E> collection) {
		if (collection == null) {
			throw new NullPointerException("collection == null");
		}

		Object[] a = collection.toArray();
		if (a.getClass() != Object[].class) {
			Object[] newArray = new Object[a.length];
			System.arraycopy(a, 0, newArray, 0, a.length);
			a = newArray;
		}
		array = a;
		size = a.length;
	}

	/**
	 * Adds the specified object at the end of this {@code ArrayList}.
	 *
	 * @param object the object to add.
	 * @return always true
	 */
	@Override
	public boolean add(E object) {
		Object[] a = array;
		int s = size;
		if (s == a.length) {
			Object[] newArray = new Object[s +
				(s < (MIN_CAPACITY_INCREMENT / 2) ?
					MIN_CAPACITY_INCREMENT : s >> 1)];
			System.arraycopy(a, 0, newArray, 0, s);
			array = a = newArray;
		}
		a[s] = object;
		size = s + 1;
		modCount++;
		return true;
	}

	/**
	 * Inserts the specified object into this {@code ArrayList} at the specified
	 * location. The object is inserted before any previous element at the
	 * specified location. If the location is equal to the size of this
	 * {@code ArrayList}, the object is added at the end.
	 *
	 * @param index  the index at which to insert the object.
	 * @param object the object to add.
	 * @throws IndexOutOfBoundsException when {@code location < 0 || location > size()}
	 */
	@Override
	public void add(int index, E object) {
		Object[] a = array;
		int s = size;
		if (index > s || index < 0) {
			throwIndexOutOfBoundsException(index, s);
		}

		if (s < a.length) {
			System.arraycopy(a, index, a, index + 1, s - index);
		} else {
			// assert s == a.length;
			Object[] newArray = new Object[newCapacity(s)];
			System.arraycopy(a, 0, newArray, 0, index);
			System.arraycopy(a, index, newArray, index + 1, s - index);
			array = a = newArray;
		}
		a[index] = object;
		size = s + 1;
		modCount++;
	}

	/**
	 * This method controls the growth of ArrayList capacities.  It represents
	 * a time-space tradeoff: we don't want to grow lists too frequently
	 * (which wastes time and fragments storage), but we don't want to waste
	 * too much space in unused excess capacity.
	 * <p/>
	 * NOTE: This method is inlined into {@link #add(Object)} for performance.
	 * If you change the method, change it there too!
	 */
	private static int newCapacity(int currentCapacity) {
		int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
			MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
		return currentCapacity + increment;
	}

	/**
	 * Adds the objects in the specified collection to this {@code ArrayList}.
	 *
	 * @param collection the collection of objects.
	 * @return {@code true} if this {@code ArrayList} is modified, {@code false}
	 * otherwise.
	 */
	@Override
	public boolean addAll(Collection<? extends E> collection) {
		Object[] newPart = collection.toArray();
		int newPartSize = newPart.length;
		if (newPartSize == 0) {
			return false;
		}
		Object[] a = array;
		int s = size;
		int newSize = s + newPartSize; // If add overflows, arraycopy will fail
		if (newSize > a.length) {
			int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
			Object[] newArray = new Object[newCapacity];
			System.arraycopy(a, 0, newArray, 0, s);
			array = a = newArray;
		}
		System.arraycopy(newPart, 0, a, s, newPartSize);
		size = newSize;
		modCount++;
		return true;
	}

	/**
	 * Inserts the objects in the specified collection at the specified location
	 * in this List. The objects are added in the order they are returned from
	 * the collection's iterator.
	 *
	 * @param index      the index at which to insert.
	 * @param collection the collection of objects.
	 * @return {@code true} if this {@code ArrayList} is modified, {@code false}
	 * otherwise.
	 * @throws IndexOutOfBoundsException when {@code location < 0 || location > size()}
	 */
	@Override
	public boolean addAll(int index, Collection<? extends E> collection) {
		int s = size;
		if (index > s || index < 0) {
			throwIndexOutOfBoundsException(index, s);
		}
		Object[] newPart = collection.toArray();
		int newPartSize = newPart.length;
		if (newPartSize == 0) {
			return false;
		}
		Object[] a = array;
		int newSize = s + newPartSize; // If add overflows, arraycopy will fail
		if (newSize <= a.length) {
			System.arraycopy(a, index, a, index + newPartSize, s - index);
		} else {
			int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
			Object[] newArray = new Object[newCapacity];
			System.arraycopy(a, 0, newArray, 0, index);
			System.arraycopy(a, index, newArray, index + newPartSize, s - index);
			array = a = newArray;
		}
		System.arraycopy(newPart, 0, a, index, newPartSize);
		size = newSize;
		modCount++;
		return true;
	}

	/**
	 * This method was extracted to encourage VM to inline callers.
	 * TODO: when we have a VM that can actually inline, move the test in here too!
	 */
	static IndexOutOfBoundsException throwIndexOutOfBoundsException(int index, int size) {
		throw new IndexOutOfBoundsException("Invalid index " + index + ", size is " + size);
	}

	/**
	 * Removes all elements from this {@code ArrayList}, leaving it empty.
	 *
	 * @see #isEmpty
	 * @see #size
	 */
	@Override
	public void clear() {
		if (size != 0) {
			Arrays.fill(array, 0, size, null);
			size = 0;
			modCount++;
		}
	}

	/**
	 * Returns a new {@code ArrayList} with the same elements, the same size and
	 * the same capacity as this {@code ArrayList}.
	 *
	 * @return a shallow copy of this {@code ArrayList}
	 * @see java.lang.Cloneable
	 */
	@Override
	public Object clone() {
		try {
			XulArrayList<E> result = (XulArrayList<E>) super.clone();
			result.array = array.clone();
			return result;
		} catch (CloneNotSupportedException e) {
			throw new AssertionError();
		}
	}

	/**
	 * Ensures that after this operation the {@code ArrayList} can hold the
	 * specified number of elements without further growing.
	 *
	 * @param minimumCapacity the minimum capacity asked for.
	 */
	public void ensureCapacity(int minimumCapacity) {
		Object[] a = array;
		if (a.length < minimumCapacity) {
			Object[] newArray = new Object[minimumCapacity];
			System.arraycopy(a, 0, newArray, 0, size);
			array = newArray;
			modCount++;
		}
	}

	@SuppressWarnings("unchecked")
	@Override
	public E get(int index) {
		if (index >= size) {
			throwIndexOutOfBoundsException(index, size);
		}
		return (E) array[index];
	}

	/**
	 * Returns the number of elements in this {@code ArrayList}.
	 *
	 * @return the number of elements in this {@code ArrayList}.
	 */
	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * Searches this {@code ArrayList} for the specified object.
	 *
	 * @param object the object to search for.
	 * @return {@code true} if {@code object} is an element of this
	 * {@code ArrayList}, {@code false} otherwise
	 */
	@Override
	public boolean contains(Object object) {
		Object[] a = array;
		int s = size;
		if (object != null) {
			for (int i = 0; i < s; i++) {
				if (object.equals(a[i])) {
					return true;
				}
			}
		} else {
			for (int i = 0; i < s; i++) {
				if (a[i] == null) {
					return true;
				}
			}
		}
		return false;
	}

	@Override
	public int indexOf(Object object) {
		Object[] a = array;
		int s = size;
		if (object != null) {
			for (int i = 0; i < s; i++) {
				if (object.equals(a[i])) {
					return i;
				}
			}
		} else {
			for (int i = 0; i < s; i++) {
				if (a[i] == null) {
					return i;
				}
			}
		}
		return -1;
	}

	@Override
	public int lastIndexOf(Object object) {
		Object[] a = array;
		if (object != null) {
			for (int i = size - 1; i >= 0; i--) {
				if (object.equals(a[i])) {
					return i;
				}
			}
		} else {
			for (int i = size - 1; i >= 0; i--) {
				if (a[i] == null) {
					return i;
				}
			}
		}
		return -1;
	}

	/**
	 * Removes the object at the specified location from this list.
	 *
	 * @param index the index of the object to remove.
	 * @return the removed object.
	 * @throws IndexOutOfBoundsException when {@code location < 0 || location >= size()}
	 */
	@Override
	public E remove(int index) {
		Object[] a = array;
		int s = size;
		if (index >= s) {
			throwIndexOutOfBoundsException(index, s);
		}
		@SuppressWarnings("unchecked") E result = (E) a[index];
		System.arraycopy(a, index + 1, a, index, --s - index);
		a[s] = null;  // Prevent memory leak
		size = s;
		modCount++;
		return result;
	}

	@Override
	public boolean remove(Object object) {
		Object[] a = array;
		int s = size;
		if (object != null) {
			for (int i = 0; i < s; i++) {
				if (object.equals(a[i])) {
					System.arraycopy(a, i + 1, a, i, --s - i);
					a[s] = null;  // Prevent memory leak
					size = s;
					modCount++;
					return true;
				}
			}
		} else {
			for (int i = 0; i < s; i++) {
				if (a[i] == null) {
					System.arraycopy(a, i + 1, a, i, --s - i);
					a[s] = null;  // Prevent memory leak
					size = s;
					modCount++;
					return true;
				}
			}
		}
		return false;
	}

	@Override
	protected void removeRange(int fromIndex, int toIndex) {
		if (fromIndex == toIndex) {
			return;
		}
		Object[] a = array;
		int s = size;
		if (fromIndex >= s) {
			throw new IndexOutOfBoundsException("fromIndex " + fromIndex
				+ " >= size " + size);
		}
		if (toIndex > s) {
			throw new IndexOutOfBoundsException("toIndex " + toIndex
				+ " > size " + size);
		}
		if (fromIndex > toIndex) {
			throw new IndexOutOfBoundsException("fromIndex " + fromIndex
				+ " > toIndex " + toIndex);
		}

		System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
		int rangeSize = toIndex - fromIndex;
		Arrays.fill(a, s - rangeSize, s, null);
		size = s - rangeSize;
		modCount++;
	}

	/**
	 * Replaces the element at the specified location in this {@code ArrayList}
	 * with the specified object.
	 *
	 * @param index  the index at which to put the specified object.
	 * @param object the object to add.
	 * @return the previous element at the index.
	 * @throws IndexOutOfBoundsException when {@code location < 0 || location >= size()}
	 */
	@Override
	public E set(int index, E object) {
		Object[] a = array;
		if (index >= size) {
			throwIndexOutOfBoundsException(index, size);
		}
		@SuppressWarnings("unchecked") E result = (E) a[index];
		a[index] = object;
		return result;
	}

	/**
	 * Returns a new array containing all elements contained in this
	 * {@code ArrayList}.
	 *
	 * @return an array of the elements from this {@code ArrayList}
	 */
	@Override
	public Object[] toArray() {
		int s = size;
		Object[] result = new Object[s];
		System.arraycopy(array, 0, result, 0, s);
		return result;
	}

	public Object[] getArray() {
		return array;
	}

	/**
	 * Returns an array containing all elements contained in this
	 * {@code ArrayList}. If the specified array is large enough to hold the
	 * elements, the specified array is used, otherwise an array of the same
	 * type is created. If the specified array is used and is larger than this
	 * {@code ArrayList}, the array element following the collection elements
	 * is set to null.
	 *
	 * @param contents the array.
	 * @return an array of the elements from this {@code ArrayList}.
	 * @throws ArrayStoreException when the type of an element in this {@code ArrayList} cannot
	 *                             be stored in the type of the specified array.
	 */
	@Override
	public <T> T[] toArray(T[] contents) {
		int s = size;
		if (contents.length < s) {
			@SuppressWarnings("unchecked") T[] newArray
				= (T[]) Array.newInstance(contents.getClass().getComponentType(), s);
			contents = newArray;
		}
		System.arraycopy(this.array, 0, contents, 0, s);
		if (contents.length > s) {
			contents[s] = null;
		}
		return contents;
	}

	/**
	 * Sets the capacity of this {@code ArrayList} to be the same as the current
	 * size.
	 *
	 * @see #size
	 */
	public void trimToSize() {
		int s = size;
		if (s == array.length) {
			return;
		}
		if (s == 0) {
			array = EMPTY_ARRAY;
		} else {
			Object[] newArray = new Object[s];
			System.arraycopy(array, 0, newArray, 0, s);
			array = newArray;
		}
		modCount++;
	}

	@Override
	public Iterator<E> iterator() {
		return new ArrayListIterator();
	}

	private class ArrayListIterator implements Iterator<E> {
		/**
		 * Number of elements remaining in this iteration
		 */
		private int remaining = size;

		/**
		 * Index of element that remove() would remove, or -1 if no such elt
		 */
		private int removalIndex = -1;

		/**
		 * The expected modCount value
		 */
		private int expectedModCount = modCount;

		public boolean hasNext() {
			return remaining != 0;
		}

		@SuppressWarnings("unchecked")
		public E next() {
			XulArrayList<E> ourList = XulArrayList.this;
			int rem = remaining;
			if (ourList.modCount != expectedModCount) {
				throw new ConcurrentModificationException();
			}
			if (rem == 0) {
				throw new NoSuchElementException();
			}
			remaining = rem - 1;
			return (E) ourList.array[removalIndex = ourList.size - rem];
		}

		public void remove() {
			Object[] a = array;
			int removalIdx = removalIndex;
			if (modCount != expectedModCount) {
				throw new ConcurrentModificationException();
			}
			if (removalIdx < 0) {
				throw new IllegalStateException();
			}
			System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
			a[--size] = null;  // Prevent memory leak
			removalIndex = -1;
			expectedModCount = ++modCount;
		}
	}

	@Override
	public int hashCode() {
		Object[] a = array;
		int hashCode = 1;
		for (int i = 0, s = size; i < s; i++) {
			Object e = a[i];
			hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
		}
		return hashCode;
	}

	@Override
	public boolean equals(Object o) {
		if (o == this) {
			return true;
		}
		if (!(o instanceof List)) {
			return false;
		}
		List<?> that = (List<?>) o;
		int s = size;
		if (that.size() != s) {
			return false;
		}
		Object[] a = array;
		if (that instanceof RandomAccess) {
			for (int i = 0; i < s; i++) {
				Object eThis = a[i];
				Object ethat = that.get(i);
				if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
					return false;
				}
			}
		} else {  // Argument list is not random access; use its iterator
			Iterator<?> it = that.iterator();
			for (int i = 0; i < s; i++) {
				Object eThis = a[i];
				Object eThat = it.next();
				if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
					return false;
				}
			}
		}
		return true;
	}

	private static final long serialVersionUID = 8683452581122892189L;

	private void writeObject(ObjectOutputStream stream) throws IOException {
		stream.defaultWriteObject();
		stream.writeInt(array.length);
		for (int i = 0; i < size; i++) {
			stream.writeObject(array[i]);
		}
	}

	private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
		stream.defaultReadObject();
		int cap = stream.readInt();
		if (cap < size) {
			throw new InvalidObjectException(
				"Capacity: " + cap + " < size: " + size);
		}
		array = cap == 0 ? EMPTY_ARRAY : new Object[cap];
		for (int i = 0; i < size; i++) {
			array[i] = stream.readObject();
		}
	}
}

